home *** CD-ROM | disk | FTP | other *** search
/ Deutsche Edition 1 / Deutsche Edition 1.iso / amok / 031-040 / amok35 / spellchecker / vorüberlegungen < prev    next >
Text File  |  1993-11-04  |  5KB  |  86 lines
  1. Einige Gedanken zur Rechtschreibprüfung.
  2. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  3. Der Name Lexikon ist eigentlich nicht ganz korrekt, denn eigentlich handelt
  4. es sich bei diesem Programm mehr um einen Duden. Der Zweck des Programmes
  5. soll es sein, Worte auf ihre korrekte Schreibweise zu überprüfen. Dazu
  6. braucht man eine Liste mit möglichst vielen richtig geschriebenen Worten.
  7. Ist das zu überprüfende Wort in der Liste vorhanden, so wird es als richtig
  8. angesehen, anderenfalls muß der Benutzer entscheiden, ob es richtig ist und
  9. ob es in die Liste aufgenommen werden soll.
  10.  
  11. Generierung der Liste:
  12. ~~~~~~~~~~~~~~~~~~~~~
  13. Die Liste muß in irgendeiner Weise geordnet sein, damit in ihr schnell
  14. gesucht werden kann. Außerdem muß sie eine variable Größe haben, damit man
  15. jederzeit Worte hinzufügen kann. Zuerst habe ich daran gedacht, einen
  16. binären (AVL) Baum zu benutzen. Er hat aber den Nachteil, daß zu jedem Wort
  17. der Liste zwei Zeiger auf Nachfolger gehören. Wird ein Wort als maximal 16
  18. Zeichen lang angenommen, so müssen mit jedem Wort zwei Pointer mit 2*4 =8
  19. Byte im Speicher gehalten werden. Auf 16 Byte Nutzinformation kommen also
  20. mindestens 8 Byte Verwaltungsinformation. Deshalb habe ich mich für ein
  21. sortiertes Array entschieden. Die variable Größe erreiche ich dadurch, daß
  22. ich nicht direkt ein Array benutze, sondern einen Pointer to Array[1..] OF
  23. String. Dann kann man den Speicher mit Allocate dynamisch je nach Bedarf
  24. anfordern. Der Nachteil ist natürlich, daß ich das Array nicht
  25. kontinuierlich vergrößern kann. Ist der allozierte Speicher voll, muß ich
  26. die Liste abspeichern, den alten Speicherbereich freigeben, einen größeren
  27. anfordern und die Liste wieder einlesen. Die Generierung der Liste geht
  28. dann folgendermaßen: Aus Textdateien, welche nur wenig Rechtschreibfehler
  29. enthalten, werden die Worte gelesen und in die Liste einsortiert. Die Liste
  30. enthält nicht nur die Worte selber, sondern auch die Häufigkeit der Worte.
  31. Sind genügend Textdateien (von verschiedenen Autoren) eingelesen, so sollte
  32. die Häufigkeit der richtig geschriebenen Worte die der falsch geschriebenen
  33. recht deutlich übersteigen. Nun braucht man nur noch die Worte geringer
  34. Häufigkeit zu löschen und schon ist die Liste fertig.
  35.  
  36. Speicherbedarf:
  37. ~~~~~~~~~~~~~~~
  38. Wenn man alle möglichen Worte, also Verben mit allen möglichen Endungen und
  39. Vorsilben und auch alle zusammemgesetzten Worte in die Liste aufnehmen
  40. wollte, so müßte man für jedes Wort wohl 30 Bytes vorsehen, und man würde
  41. wohl leicht über 100.000 verschiedene Worte finden. Damit wäre das Array
  42. 30*100.000 = 3 MByte groß. Deshalb müssen wir also zusammengesetzte Worte
  43. in ihre Komponenten zerlegen und auch einige Vorsilben (z.B. vor- auf- )
  44. getrennt speichern. Dann müßte eine Wortlänge von ca. 16 Zeichen reichen
  45. und mit ca. 10- 20000 Worten sollte sich dann der Grundwortschatz abdecken
  46. lassen. Damit wäre das Array 10000*16 = 160.000 Bytes groß. Auf Diskette
  47. wird man dann nicht das ganze Array, sondern die einzelnen Worte speichern.
  48. Da die Worte im Mittel kleiner als die Maximallänge von 16 Bytes sind, wird
  49. das File deutlich kleiner als das Array sein.
  50.  
  51. Stefan Salewski, 11.2.90
  52.  
  53.  
  54. Probleme:
  55. ~~~~~~~~~
  56. Bei der Generierung des Lexikons sollen zusammengesetzte Wörter in ihre
  57. Komponenten zerlegt werden. Die Zerlegung eines Wortes geschieht
  58. folgendermaßen: Wenn ein Wort in der Liste nicht gefunden wird, wird von
  59. dem Wort solange der letzte Buchstabe abgeschnitten, bis das vordere
  60. Teilstück entweder in der Liste gefunden wird oder leer ist. Wird das
  61. vordere Teilstück gefunden, so wird von dem ursprünglichen Wort dieser
  62. vordere Teil entfernt und mit dem Rest wird in der gleichen Weise
  63. verfahren. Bleibt ein Rest des Wortes übrig, der in der Liste nicht
  64. gefunden wird, so wird der Rest (oder das ganze urspüngliche Wort) in die
  65. Liste übernommen.
  66.  
  67. Beispiel: Gesucht wird Haustür
  68. Haustür wird nicht gefunden. r-ü-t werden nacheinander abgespalten. Dann
  69. bleibt Haus übrig und wird in der Liste gefunden. Nun wird Haus aus Haustür
  70. herausgelöscht, es bleibt tür. Da Haustür großgeschrieben ist, muß auch das
  71. t von tür in einen großen Buchstaben umgewandelt werden. Es bleibt Tür.
  72. Wird Tür in der Liste gefunden, so ist Haustür also in Komponenten in der
  73. Liste schon vorhanden, andernfalls muß Tür noch eingefügt werden.
  74.  
  75. Komponenten können natürlich erst dann als solche erkannt werden, wenn sie
  76. schon in der Liste enthalten sind. Deshalb müssen die Quelltexte mehrmals
  77. gelesen werden. Zuerst werden nur Worte übernommen, die nur aus zwei
  78. Buchstaben bestehen, beim nächsten Durchlauf dann die Worte die aus 3
  79. Buchstaben bestehen usw.
  80.  
  81. Stefan Salewski, 12.2.90
  82.  
  83.  
  84.  
  85.  
  86.